package com.baixiaowen.xiaoaointerview.Java编程功底篇.手写树算法;


import java.util.LinkedList;

/**
 * 手写二叉搜索数
 *
 * @author Baixiaowen
 */
public class BSTree<T extends Comparable<T>> {

    BSTNode<T> root = null;

    static class BSTNode<T> {
        BSTNode<T> left = null;
        BSTNode<T> right = null;

        T data;

        public BSTNode(T data) {
            this.data = data;
        }
    }

    private void add(BSTNode<T> node, BSTNode<T> element) {
        if (element.data.compareTo(node.data) <= 0) {
            if (node.left == null) {
                node.left = element;
                return;
            }
            add(node.left, element);
        } else {
            if (node.right == null) {
                node.right = element;
                return;
            }
            add(node.right, element);
        }
    }

    public void add(T element) {
        BSTNode<T> node = new BSTNode<>(element);
        if (root == null) {
            root = node;
            return;
        }

        add(root, node);
    }

    // 前序遍历
    public static <T> void perOrder(BSTNode<T> node) {

        if (node == null) {
            return;
        }

        System.err.println(node.data);
        perOrder(node.left);
        perOrder(node.right);

    }

    // 后续遍历
    public static <T> void postOrder(BSTNode<T> node) {

        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.err.println(node.data);

    }

    // 中序遍历
    public static <T> void inOrder(BSTNode<T> node) {

        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.err.println(node.data);
        inOrder(node.right);

    }

    // 二叉树反转
    public static <T> void reverse(BSTNode<T> node) {

        if (node == null) {
            return;
        }

        BSTNode t = node.left;
        node.left = node.right;
        node.right = t;

        reverse(node.left);
        reverse(node.right);

    }

    // 广度优先搜索
    public static <T> void bfs(BSTNode<T> node) {

        LinkedList<BSTNode<T>> queue = new LinkedList<BSTNode<T>>();
        queue.add(node);

        while (queue.size() > 0) {
            BSTNode<T> item = queue.pop();
            System.err.println(item.data);

            if (item.left != null) {
                queue.add(item.left);
            }

            if (item.right != null) {
                queue.add(item.right);
            }
        }

    }

    public static void main(String[] args) {
//        BSTree<Integer> tree = new BSTree<>();
//
//        tree.add(10);
//        tree.add(7);
//        tree.add(5);
//        tree.add(8);
//        tree.add(15);
//        tree.add(30);
//        tree.add(21);
//
//        TreePrinter printer = new TreePrinter();
//        printer.print(tree.root);
//
//        perOrder(tree.root);
//        System.err.println("-------");
//        inOrder(tree.root);
//        System.err.println("-------");
//        postOrder(tree.root);

        // 测试反转
//        test_reverse();

        // 广度优先搜索
        BSTree<Integer> tree = new BSTree<>();

        tree.add(10);
        tree.add(7);
        tree.add(5);
        tree.add(8);
        tree.add(15);
        tree.add(30);
        tree.add(21);

        TreePrinter printer = new TreePrinter();
        printer.print(tree.root);

        bfs(tree.root );

    }

    public static void test_reverse() {
        BSTree tree = new BSTree();

        tree.add(10);
        tree.add(7);
        tree.add(5);
        tree.add(8);
        tree.add(15);
        tree.add(30);
        tree.add(21);

        TreePrinter printer = new TreePrinter();
        printer.print(tree.root);

        reverse(tree.root);
        printer.print(tree.root);

    }

}
